package sort;

/**
 * @author wcj
 * @Date 2021/7/7 1:31
 * @Version 1.0
 */
public class ShellSort {

    /**
     * 希尔排序：分组的直接插入排序
     *
     * @param arr
     * @return
     */
    public static int[] shellSort(int[] arr) {
        int increment = arr.length;
        do {
            increment = increment / 3 - 1;
            for (int i = increment; i < arr.length; i += increment) {
                int tmp = arr[i];
                int j = 0;
                for (j = i - increment; j >= 0 && arr[j] > tmp; j -= increment) {
                    arr[j + increment] = arr[j];
                }
                arr[j + increment] = tmp;
            }
        } while (increment > 1);
        return arr;
    }
}
